/*
Date:20210407 0:24 pm

*/
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) 
    {
        if(heights.size()==0)
        {
            return 0;
        }
        //如果一开始就单调递减，那些后面的元素就不知道可以从头开始，因为栈里面它们底下没有东西，因此一开始压入0，保证最底下一直有东西。还有就是注意下标是怎么减出宽度的。
        heights.insert(heights.begin(),0);
        //最后的哨兵0是让它原末尾能停止
        heights.push_back(0);
        stack<int>S;
        S.push(0);
        int Max=0;
        int square;
        for(int i=1;i<heights.size();i++)
        {
            if(heights[S.top()]<=heights[i])
            {
                S.push(i);
            }
            else
            {
                while(!S.empty()&&heights[S.top()]>heights[i])
                {
                    //更新
                    int now=S.top();
                    S.pop();
                    square=heights[now]*(i-S.top()-1);
                    if(square>Max)
                    {
                        Max=square;
                    }

                    
                }
                S.push(i);
            }
        }
        return Max;
    }
};